use std::u64;

use crate::collections::chain::{ChainBase, Search};
use crate::collections::common::SearchTreeBase;

pub trait MapBase<T> {
    fn new(vexes: Vec<T>, is_directed: bool) -> Self;
    fn index(&self, vex: T) -> Option<u64>;
    fn insert_vex(&mut self, vex: T);
    fn update_edge(&mut self, from: T, to: T, weight: u64);
    fn edge(&self, from: T, to: T) -> Option<u64>;
    fn delete_edge(&mut self, from: T, to: T);
    fn delete_vex(&mut self, vex: T);
    fn clear(&mut self);
    fn size(&self) -> u64;
    fn size_of_edge(&self) -> u64;
    fn weight_of_vex(&self, vex: T) -> Option<u64>;
    fn minimal(&self, vex: Option<T>) -> Self;
    fn shortest_path(&self, from: T, to: T) -> (Vec<T>, u64);
    fn toposort(&self) -> Vec<T>;
    fn criticular_path(&self) -> Self;
}

pub trait MapIterator<T>: MapBase<T> {
    fn edges(&self, vex: T) -> Vec<(T, u64)>;

    fn bfs_iter(&self, vex: T) -> BfsIter<Self, T>
    where
        Self: Sized,
        T: Clone,
    {
        let index = self.index(vex.clone()).unwrap() as usize;
        let mut marker = vec![true; self.size() as usize];
        let mut que = Vec::<T>::with_capacity(self.size() as usize);
        que.push(vex);
        marker[index] = false;
        BfsIter {
            map: self,
            avail: marker,
            queue: que,
        }
    }

    fn dfs_iter(&self, vex: T) -> DfsIter<Self, T>
    where
        Self: Sized,
        T: Clone,
    {
        let index = self.index(vex.clone()).unwrap() as usize;
        let mut marker = vec![true; self.size() as usize];
        let mut stk = Vec::<T>::with_capacity(self.size() as usize);
        stk.push(vex);
        marker[index] = false;
        DfsIter {
            map: self,
            avail: marker,
            stack: stk,
        }
    }
}

pub struct BfsIter<'a, M, T> {
    map: &'a M,
    avail: Vec<bool>,
    queue: Vec<T>,
}

pub struct DfsIter<'a, M, T> {
    map: &'a M,
    avail: Vec<bool>,
    stack: Vec<T>,
}

impl<M, T> Iterator for BfsIter<'_, M, T>
where
    T: Copy + Default + Sized,
    M: MapBase<T> + MapIterator<T>,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.queue.len() > 0 {
            let vex = self.queue.remove(0);
            self.map.edges(vex).into_iter().for_each(|(v, _)| {
                let idx = self.map.index(v).unwrap() as usize;
                if self.avail[idx] {
                    self.avail[idx] = false;
                    self.queue.push(v);
                }
            });
            return Some(vex);
        }
        None
    }
}

impl<M, T> Iterator for DfsIter<'_, M, T>
where
    T: Copy + Default + Sized,
    M: MapBase<T> + MapIterator<T>,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.stack.pop().map(|vex| {
            self.map.edges(vex).into_iter().for_each(|(v, _)| {
                let idx = self.map.index(v).unwrap() as usize;
                if self.avail[idx] {
                    self.avail[idx] = false;
                    self.stack.push(v);
                }
            });
            vex
        })
    }
}

pub struct Vexes<C, T> {
    nodes: C,
    lines: u64,
    directed: bool,
    weights: Vec<T>,
}

impl<C, T> Vexes<C, T> {
    // O(n*n)
    #[inline]
    fn prim<K>(&self, mut vex: K) -> Self
    where
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        assert!(!self.directed);
        let mut n = C::new();
        let mut e = Vec::<T>::with_capacity(self.nodes.size() as usize);
        let cache = self.nodes.to_vector();
        let mut size = 0;
        if let Some(mut idx) = self.nodes.index(&vex) {
            n.push(vex);
            e.push(T::new());
            let mut edges = Vec::<(usize, bool, u64)>::with_capacity(self.nodes.size() as usize);
            for _ in 0..self.nodes.size() {
                edges.push((0usize, true, u64::MAX));
            }
            edges[idx as usize].1 = false;
            for _ in 1..self.nodes.size() {
                self.weights[idx as usize]
                    .to_vector()
                    .iter()
                    .for_each(|(k, v)| {
                        let idx_y = self.nodes.index(k).unwrap() as usize;
                        if edges[idx_y].1 && edges[idx_y].2 > *v {
                            edges[idx_y].2 = *v;
                            edges[idx_y].0 = idx as usize;
                        }
                    });
                let (idx_to, &(idx_from, _, weight)) = edges
                    .iter()
                    .enumerate()
                    .min_by_key(|(_, edge)| match edge.1 {
                        true => edge.2,
                        false => u64::MAX,
                    })
                    .unwrap();
                idx = idx_to as u64;
                vex = cache[idx_to];
                n.push(vex);
                e.push(T::new());
                e[idx_from].insert(vex, weight);
                e[idx_to].insert(cache[idx_from], weight);
                edges[idx_to].1 = false;
            }
            size = self.nodes.size() - 1;
        }
        Self {
            nodes: n,
            lines: size,
            directed: false,
            weights: e,
        }
    }

    //)(n*log(n))
    #[inline]
    fn kruskal<K>(&self) -> Self
    where
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        assert!(!self.directed);
        let node_size = self.nodes.size() as usize;
        let mut n = C::new();
        let mut e = Vec::<T>::with_capacity(node_size);
        let cache = self.nodes.to_vector();
        let mut edges = Vec::<(usize, usize, u64)>::with_capacity(self.lines as usize);
        let mut set_table = vec![(K::default(), 0usize); node_size];
        set_table
            .iter_mut()
            .enumerate()
            .for_each(|(idx, x)| *x = (cache[idx], idx));
        for i in 0..node_size {
            edges.append(
                &mut self.weights[i]
                    .to_vector()
                    .into_iter()
                    .map(|(k, v)| (i, self.nodes.index(&k).unwrap() as usize, v))
                    .collect(),
            )
        }
        edges.sort_by_key(|&(_, _, weight)| weight);
        let (mut idx, _, _) = edges[0];
        n.push(set_table[idx].0);
        e.push(T::new());
        idx = 0;
        while n.size() < self.nodes.size() {
            let (idx_from, idx_to, weight) = edges[idx];
            let (set_to, set_from) = (set_table[idx_to].1, set_table[idx_from].1);
            if set_from != set_to {
                set_table
                    .iter_mut()
                    .filter(|(_, s)| *s == set_to)
                    .for_each(|(_, s)| *s = set_from);
                n.push(set_table[idx_to].0);
                e.push(T::new());
                e[idx_from].insert(set_table[idx_to].0, weight);
                e[idx_to].insert(set_table[idx_from].0, weight);
            }
            idx += 1;
        }

        Self {
            nodes: n,
            lines: self.nodes.size() - 1,
            directed: false,
            weights: e,
        }
    }

    // O(n*n*n)
    #[inline]
    fn djikstra<K>(&self, vex: K) -> (Vec<u64>, Vec<Option<u64>>)
    where
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        let node_size = self.nodes.size() as usize;
        let mut distance = vec![u64::MAX; node_size];
        let mut prec: Vec<Option<u64>> = vec![None; node_size];
        if let Some(idx) = self.nodes.index(&vex) {
            let idx_from = idx as usize;
            let mut available = vec![u64::MAX; node_size];
            distance[idx_from] = 0;
            self.weights[idx_from]
                .to_vector()
                .into_iter()
                .for_each(|(k, w)| {
                    let idx = self.nodes.index(&k).unwrap() as usize;
                    distance[idx] = w;
                    available[idx] = w;
                    prec[idx] = Some(idx_from as u64);
                });
            while let Some((idx_from, _)) = available.iter().enumerate().min_by_key(|(_, w)| **w) {
                match available[idx_from] {
                    u64::MAX => break,
                    _ => available[idx_from] = u64::MAX,
                }
                self.weights[idx_from]
                    .to_vector()
                    .into_iter()
                    .for_each(|(k, w)| {
                        let idx = self.nodes.index(&k).unwrap() as usize;
                        if distance[idx] > distance[idx_from] + w {
                            distance[idx] = distance[idx_from] + w;
                            available[idx] = distance[idx_from] + w;
                            prec[idx] = Some(idx_from as u64);
                        }
                    });
            }
        }
        (distance, prec)
    }

    #[inline]
    pub fn fit<K>(&mut self)
    where
        K: Copy + Ord + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        let mut in_degrees = vec![0u64; self.nodes.size() as usize];
        for i in 0..(self.nodes.size() as usize) {
            self.weights[i]
                .to_vector()
                .into_iter()
                .for_each(|(to, _)| in_degrees[self.nodes.index(&to).unwrap() as usize] += 1);
        }
        let mut iter = in_degrees
            .into_iter()
            .enumerate()
            .rev()
            .filter(|(_, x)| *x == 0);
        while let Some((idx, _)) = iter.next() {
            if self.weights[idx].size() == 0 {
                self.weights.remove(idx);
                self.nodes.delete(idx as u64);
            }
        }
    }

    #[inline]
    pub fn to_matrix<K>(mut self) -> Matrix<C>
    where
        K: Copy + Ord + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        let mut matrix = Matrix::new(self.nodes.to_vector(), self.directed);
        self.weights.iter().enumerate().for_each(|(idx, edges)| {
            let from = self.nodes.at(idx as u64).unwrap();
            edges
                .to_vector()
                .into_iter()
                .for_each(|(to, w)| matrix.update_edge(from, to, w));
        });
        self.clear();
        matrix
    }
}

impl<K, C, T> MapBase<K> for Vexes<C, T>
where
    K: Copy + Ord + Default + Sized,
    C: ChainBase<K> + Search<K>,
    T: SearchTreeBase<K, u64>,
{
    #[inline]
    fn new(vexes: Vec<K>, is_directed: bool) -> Self {
        let mut n = C::new();
        let mut e = Vec::<T>::with_capacity(vexes.len());
        vexes.into_iter().for_each(|vex| {
            n.push(vex);
            e.push(T::new());
        });
        Self {
            nodes: n,
            lines: 0,
            directed: is_directed,
            weights: e,
        }
    }

    #[inline]
    fn index(&self, vex: K) -> Option<u64> {
        self.nodes.index(&vex)
    }

    #[inline]
    fn insert_vex(&mut self, vex: K) {
        if self.nodes.index(&vex).is_none() {
            self.nodes.push(vex);
            self.weights.push(T::new());
        }
    }

    #[inline]
    fn update_edge(&mut self, from: K, to: K, weight: u64) {
        assert!(weight > 0);
        if let (Some(idx_from), Some(idx_to)) = (self.nodes.index(&from), self.nodes.index(&to)) {
            match self.weights[idx_from as usize].insert(to, weight) {
                true => self.lines += 1,
                false => self.weights[idx_from as usize].update(to, weight),
            }
            if !self.directed {
                if !self.weights[idx_to as usize].insert(from, weight) {
                    self.weights[idx_to as usize].update(from, weight);
                }
            }
        }
    }

    #[inline]
    fn edge(&self, from: K, to: K) -> Option<u64> {
        if let Some(idx_from) = self.nodes.index(&from) {
            self.weights[idx_from as usize].query(to)
        } else {
            None
        }
    }

    #[inline]
    fn delete_edge(&mut self, from: K, to: K) {
        if let (Some(idx_from), Some(idx_to)) = (self.nodes.index(&from), self.nodes.index(&to)) {
            if self.weights[idx_from as usize].delete(to) {
                self.lines -= 1;
                if !self.directed {
                    self.weights[idx_to as usize].delete(from);
                }
            }
        }
    }

    #[inline]
    fn delete_vex(&mut self, vex: K) {
        if let Some(idx) = self.nodes.index(&vex) {
            let mut tree = self.weights.remove(idx as usize);
            if self.directed {
                let sum: u64 = self
                    .weights
                    .iter_mut()
                    .map(|other| other.delete(vex) as u64)
                    .sum();
                self.lines -= sum;
            } else {
                let idxes = tree
                    .where_key(|_| true)
                    .iter()
                    .map(|k| self.nodes.index(k).unwrap() as usize)
                    .collect::<Vec<_>>();
                idxes.into_iter().for_each(|idx| {
                    self.weights[idx].delete(vex);
                });
            }
            self.lines -= tree.size() as u64;
            tree.clear();
        }
    }

    #[inline]
    fn clear(&mut self) {
        self.weights.iter_mut().for_each(|vex| vex.clear());
        self.weights.clear();
        self.nodes.clear();
        self.lines = 0;
    }

    #[inline]
    fn size(&self) -> u64 {
        self.nodes.size()
    }

    #[inline]
    fn size_of_edge(&self) -> u64 {
        self.lines
    }

    #[inline]
    fn weight_of_vex(&self, vex: K) -> Option<u64> {
        self.nodes
            .index(&vex)
            .map(|idx| self.weights[idx as usize].where_val(|_| true).iter().sum())
    }

    #[inline]
    fn minimal(&self, vex: Option<K>) -> Self {
        match vex {
            Some(v) => self.prim(v),
            None => self.kruskal(),
        }
    }

    #[inline]
    fn shortest_path(&self, from: K, to: K) -> (Vec<K>, u64) {
        let (distance, prec) = self.djikstra(from);
        let mut idx_to = self.nodes.index(&to).unwrap() as usize;
        let dis = distance[idx_to];
        let mut path = Vec::<K>::new();
        path.push(to);
        while let Some(idx_v) = prec[idx_to] {
            path.insert(0, self.nodes.at(idx_v).unwrap());
            idx_to = idx_v as usize;
        }
        (path, dis)
    }

    #[inline]
    fn toposort(&self) -> Vec<K> {
        assert!(self.directed);
        let node_size = self.nodes.size() as usize;
        let mut sequence = Vec::<K>::with_capacity(node_size);
        let mut in_degrees = vec![0u64; node_size];
        let mut stack = Vec::<usize>::with_capacity(node_size);
        for i in 0..node_size {
            self.weights[i]
                .to_vector()
                .into_iter()
                .for_each(|(to, _)| in_degrees[self.nodes.index(&to).unwrap() as usize] += 1);
        }
        stack.append(
            &mut in_degrees
                .iter()
                .enumerate()
                .filter(|(_, x)| **x == 0)
                .map(|(idx, _)| idx)
                .collect::<Vec<_>>(),
        );
        let mut count = 0;
        while let Some(idx) = stack.pop() {
            self.weights[idx]
                .to_vector()
                .into_iter()
                .for_each(|(to, _)| {
                    let idx_to = self.nodes.index(&to).unwrap() as usize;
                    match in_degrees[idx_to] == 1 {
                        true => stack.push(idx_to),
                        false => in_degrees[idx_to] -= 1,
                    }
                });
            sequence.push(self.nodes.at(idx as u64).unwrap());
            count += 1;
        }
        assert!(count == self.nodes.size(), "circled graph exists");
        sequence
    }

    #[inline]
    fn criticular_path(&self) -> Self {
        assert!(self.directed);
        let node_size = self.nodes.size() as usize;
        let mut counts = 0;
        let mut n = C::new();
        let mut e = Vec::<T>::with_capacity(node_size);
        let mut earliest = vec![0u64; node_size];
        let mut latest = vec![u64::MAX; node_size];
        let sequence = self
            .toposort()
            .into_iter()
            .map(|k| {
                n.push(k);
                e.push(T::new());
                self.nodes.index(&k).unwrap() as usize
            })
            .collect::<Vec<_>>();
        for &idx in sequence.iter() {
            self.weights[idx]
                .to_vector()
                .into_iter()
                .for_each(|(to, time)| {
                    let idx_to = self.nodes.index(&to).unwrap() as usize;
                    if earliest[idx] + time > earliest[idx_to] {
                        earliest[idx_to] = earliest[idx] + time;
                    }
                });
        }
        latest[node_size - 1] = earliest[node_size - 1];
        for &idx in sequence.iter().rev() {
            self.weights[idx]
                .to_vector()
                .into_iter()
                .for_each(|(to, time)| {
                    let idx_to = self.nodes.index(&to).unwrap() as usize;
                    if latest[idx] > latest[idx_to] - time {
                        latest[idx] = latest[idx_to] - time;
                    }
                });
        }
        for &idx in sequence.iter() {
            self.weights[idx]
                .to_vector()
                .into_iter()
                .for_each(|(to, time)| {
                    let idx_to = self.nodes.index(&to).unwrap() as usize;
                    if earliest[idx] + time == latest[idx_to] {
                        e[idx].insert(to, time);
                        counts += 1;
                    }
                });
        }
        let mut res = Self {
            nodes: n,
            lines: counts,
            directed: false,
            weights: e,
        };
        res.fit();
        res
    }
}

impl<K, C, T> MapIterator<K> for Vexes<C, T>
where
    K: Copy + Ord + Default + Sized,
    C: ChainBase<K> + Search<K>,
    T: SearchTreeBase<K, u64>,
{
    #[inline]
    fn edges(&self, vex: K) -> Vec<(K, u64)> {
        if let Some(idx) = self.nodes.index(&vex) {
            self.weights[idx as usize].to_vector()
        } else {
            Vec::<(K, u64)>::new()
        }
    }
}

pub struct Matrix<C> {
    nodes: C,
    lines: u64,
    directed: bool,
    weight: Vec<Vec<u64>>,
}

impl<C> Matrix<C> {
    #[inline]
    fn prim<K>(&self, mut vex: K) -> Self
    where
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
    {
        assert!(!self.directed);
        let mut n = C::new();
        let num_keys = self.nodes.size() as usize;
        let mut e = Vec::<Vec<u64>>::with_capacity(num_keys);
        let mut size = 0;
        if let Some(mut idx) = self.nodes.index(&vex) {
            n.push(vex);
            e.push(vec![0u64; num_keys]);
            let mut edges = Vec::<(usize, bool, u64)>::with_capacity(self.nodes.size() as usize);
            for _ in 0..self.nodes.size() {
                edges.push((0usize, true, u64::MAX));
            }
            edges[idx as usize].1 = false;
            for _ in 1..self.nodes.size() {
                self.weight[idx as usize]
                    .iter()
                    .enumerate()
                    .for_each(|(idx_y, v)| {
                        if edges[idx_y].1 && edges[idx_y].2 > *v {
                            edges[idx_y].2 = *v;
                            edges[idx_y].0 = idx as usize;
                        }
                    });
                let (idx_to, &(idx_from, _, weight)) = edges
                    .iter()
                    .enumerate()
                    .min_by_key(|(_, edge)| match edge.1 {
                        true => edge.2,
                        false => u64::MAX,
                    })
                    .unwrap();
                idx = idx_to as u64;
                vex = self.nodes.at(idx).unwrap();
                n.push(vex);
                e.push(vec![0u64; num_keys]);
                e[idx_from][idx_to] = weight;
                e[idx_to][idx_from] = weight;
                edges[idx_to].1 = false;
            }
            size = self.nodes.size() - 1;
        }
        Self {
            nodes: n,
            lines: size,
            directed: false,
            weight: e,
        }
    }

    #[inline]
    fn kruskal<K>(&self) -> Self
    where
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
    {
        assert!(!self.directed);
        let mut n = C::new();
        let num_keys = self.nodes.size() as usize;
        let mut e = Vec::<Vec<u64>>::with_capacity(num_keys);
        let cache = self.nodes.to_vector();
        let mut edges = Vec::<(usize, usize, u64)>::with_capacity(self.lines as usize);
        let mut set_table = vec![0usize; num_keys];
        set_table
            .iter_mut()
            .enumerate()
            .for_each(|(idx, x)| *x = idx);
        for i in 0..(self.nodes.size() as usize) {
            edges.append(
                &mut self.weight[i]
                    .iter()
                    .enumerate()
                    .filter(|(_, w)| **w > 0)
                    .map(|(k, &w)| (i, k, w))
                    .collect(),
            )
        }
        edges.sort_by_key(|&(_, _, weight)| weight);
        let (mut idx, _, _) = edges[0];
        n.push(cache[idx]);
        e.push(vec![0u64; num_keys]);
        idx = 0;
        while n.size() < self.nodes.size() {
            let (idx_from, idx_to, weight) = edges[idx];
            if set_table[idx_from] != set_table[idx_to] {
                set_table[idx_to] = set_table[idx_from];
                n.push(cache[idx_to]);
                e.push(vec![0u64; num_keys]);
                e[idx_from][idx_to] = weight;
                e[idx_to][idx_from] = weight;
            }
            idx += 1;
        }

        Self {
            nodes: n,
            lines: self.nodes.size() - 1,
            directed: false,
            weight: e,
        }
    }

    #[inline]
    fn floyed<K>(&self) -> (Vec<Vec<u64>>, Vec<Vec<usize>>)
    where
        Self: MapBase<K>,
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
    {
        let mut n = C::new();
        let len = self.nodes.size() as usize;
        let mut shortest = Vec::<Vec<u64>>::with_capacity(len);
        let mut routes = Vec::<Vec<usize>>::with_capacity(len);
        self.nodes
            .to_vector()
            .into_iter()
            .enumerate()
            .for_each(|(idx, vex)| {
                n.push(vex);
                let mut rot = vec![0usize; len];
                let mut distance = self.weight[idx].clone();
                distance.iter_mut().enumerate().for_each(|(col, d)| {
                    if *d == 0 {
                        *d = u64::MAX;
                    } else {
                        rot[col] = idx;
                    }
                });
                routes.push(rot);
                shortest.push(distance);
            });
        for k in 0..len {
            for i in 0..len {
                for j in 0..len {
                    if k != i && k != j && i != j {
                        if shortest[i][k] + shortest[k][j] < shortest[i][j] {
                            shortest[i][j] = shortest[i][k] + shortest[k][j];
                            routes[i][j] = routes[k][j];
                        }
                    }
                }
            }
        }
        (shortest, routes)
    }

    #[inline]
    fn fit<K>(&mut self)
    where
        Self: MapBase<K>,
        K: Copy + Default + Sized,
        C: ChainBase<K> + Search<K>,
    {
        let mut in_degrees = vec![0u64; self.nodes.size() as usize];
        for i in 0..(self.nodes.size() as usize) {
            self.weight[i]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, _)| in_degrees[to] += 1);
        }
        let mut iter = in_degrees
            .into_iter()
            .enumerate()
            .rev()
            .filter(|(_, x)| *x == 0);
        while let Some((idx, _)) = iter.next() {
            if self.weight[idx].iter().sum::<u64>() == 0 {
                self.delete_vex(self.nodes.at(idx as u64).unwrap());
            }
        }
    }

    #[inline]
    pub fn to_vexes<K, T>(mut self) -> Vexes<C, T>
    where
        Self: MapBase<K>,
        K: Copy + Ord + Default + Sized,
        C: ChainBase<K> + Search<K>,
        T: SearchTreeBase<K, u64>,
    {
        let cache = self.nodes.to_vector();
        let mut vexes = Vexes::new(cache.clone(), self.directed);
        self.weight
            .iter()
            .enumerate()
            .for_each(|(idx_from, edges)| {
                let from = cache[idx_from];
                edges
                    .into_iter()
                    .enumerate()
                    .filter(|(_, w)| **w > 0)
                    .for_each(|(idx_to, &w)| vexes.update_edge(from, cache[idx_to], w));
            });
        self.clear();
        vexes
    }
}

impl<K, C> MapBase<K> for Matrix<C>
where
    K: Copy + Ord + Default + Sized,
    C: ChainBase<K> + Search<K>,
{
    #[inline]
    fn new(vexes: Vec<K>, is_directed: bool) -> Self {
        let mut n = C::new();
        let len = vexes.len();
        let mut vecs = Vec::<Vec<u64>>::with_capacity(len);
        vexes.into_iter().for_each(|vex| {
            n.push(vex);
            vecs.push(vec![0u64; len]);
        });
        Self {
            nodes: n,
            lines: 0,
            directed: is_directed,
            weight: vecs,
        }
    }

    #[inline]
    fn index(&self, vex: K) -> Option<u64> {
        self.nodes.index(&vex)
    }

    #[inline]
    fn insert_vex(&mut self, vex: K) {
        self.nodes.push(vex);
        self.weight
            .iter_mut()
            .for_each(|v| v.resize(v.len() + 1, 0u64));
        self.weight.push(vec![0u64; self.nodes.size() as usize]);
    }

    #[inline]
    fn update_edge(&mut self, from: K, to: K, weight: u64) {
        assert!(weight > 0);
        if let (Some(idx_from), Some(idx_to)) = (self.nodes.index(&from), self.nodes.index(&to)) {
            self.lines += 1;
            self.weight[idx_from as usize][idx_to as usize] = weight;
            if !self.directed {
                self.weight[idx_to as usize][idx_from as usize] = weight;
            }
        }
    }

    #[inline]
    fn edge(&self, from: K, to: K) -> Option<u64> {
        if let (Some(idx_from), Some(idx_to)) = (self.nodes.index(&from), self.nodes.index(&to)) {
            match self.weight[idx_from as usize][idx_to as usize] {
                0 => None,
                w => Some(w),
            }
        } else {
            None
        }
    }

    #[inline]
    fn delete_edge(&mut self, from: K, to: K) {
        if let (Some(idx_from), Some(idx_to)) = (self.nodes.index(&from), self.nodes.index(&to)) {
            self.lines -= 1;
            self.weight[idx_from as usize][idx_to as usize] = 0;
            if !self.directed {
                self.weight[idx_to as usize][idx_from as usize] = 0;
            }
        }
    }

    #[inline]
    fn delete_vex(&mut self, vex: K) {
        if let Some(idx) = self.nodes.index(&vex) {
            let mut sum = self.weight[idx as usize].iter().filter(|x| **x > 0).count();
            self.weight.remove(idx as usize);
            if self.directed {
                sum += self.weight.iter_mut().fold(0usize, |mut accum, v| {
                    accum += (v[idx as usize] > 0) as usize;
                    v.remove(idx as usize);
                    accum
                });
            }
            self.lines -= sum as u64;
            self.nodes.delete(idx);
        }
    }

    #[inline]
    fn clear(&mut self) {
        self.weight.clear();
        self.nodes.clear();
        self.lines = 0;
    }

    #[inline]
    fn size(&self) -> u64 {
        self.nodes.size()
    }

    #[inline]
    fn size_of_edge(&self) -> u64 {
        self.lines
    }

    #[inline]
    fn weight_of_vex(&self, vex: K) -> Option<u64> {
        self.nodes
            .index(&vex)
            .map(|idx| self.weight[idx as usize].iter().sum())
    }

    #[inline]
    fn minimal(&self, vex: Option<K>) -> Self {
        match vex {
            Some(v) => self.prim(v),
            None => self.kruskal(),
        }
    }

    #[inline]
    fn shortest_path(&self, from: K, to: K) -> (Vec<K>, u64) {
        let (distance, routes) = self.floyed();
        let idx_from = self.nodes.index(&from).unwrap() as usize;
        let mut idx_to = self.nodes.index(&to).unwrap() as usize;
        let dis = distance[idx_from][idx_to];
        let mut path = Vec::<K>::new();
        path.push(to);
        while idx_from != idx_to {
            idx_to = routes[idx_from][idx_to];
            path.insert(0, self.nodes.at(idx_to as u64).unwrap());
        }
        (path, dis)
    }

    #[inline]
    fn toposort(&self) -> Vec<K> {
        assert!(self.directed);
        let node_size = self.nodes.size() as usize;
        let mut sequence = Vec::<K>::with_capacity(node_size);
        let mut in_degrees = vec![0u64; node_size];
        let mut stack = Vec::<usize>::with_capacity(node_size);
        for i in 0..node_size {
            self.weight[i]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, _)| in_degrees[to] += 1);
        }
        stack.append(
            &mut in_degrees
                .iter()
                .enumerate()
                .filter(|(_, x)| **x == 0)
                .map(|(idx, _)| idx)
                .collect::<Vec<_>>(),
        );
        let mut count = 0;
        while let Some(idx) = stack.pop() {
            self.weight[idx]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, _)| match in_degrees[to] == 1 {
                    true => stack.push(to),
                    false => in_degrees[to] -= 1,
                });
            sequence.push(self.nodes.at(idx as u64).unwrap());
            count += 1;
        }
        assert!(count == self.nodes.size(), "circled graph exists");
        sequence
    }

    #[inline]
    fn criticular_path(&self) -> Self {
        assert!(self.directed);
        let node_size = self.nodes.size() as usize;
        let mut counts = 0;
        let mut n = C::new();
        let mut e = Vec::<Vec<u64>>::with_capacity(node_size);
        let mut earliest = vec![0u64; node_size];
        let mut latest = vec![u64::MAX; node_size];
        let sequence = self
            .toposort()
            .into_iter()
            .map(|k| {
                n.push(k);
                e.push(vec![0u64; node_size]);
                self.nodes.index(&k).unwrap() as usize
            })
            .collect::<Vec<_>>();
        for &idx in sequence.iter() {
            self.weight[idx]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, &time)| {
                    if earliest[idx] + time > earliest[to] {
                        earliest[to] = earliest[idx] + time;
                    }
                });
        }
        latest[node_size - 1] = earliest[node_size - 1];
        for &idx in sequence.iter().rev() {
            self.weight[idx]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, &time)| {
                    if latest[idx] > latest[to] - time {
                        latest[idx] = latest[to] - time;
                    }
                });
        }
        for &idx in sequence.iter() {
            self.weight[idx]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .for_each(|(to, &time)| {
                    if earliest[idx] + time == latest[to] {
                        e[idx][to] = time;
                        counts += 1;
                    }
                });
        }
        let mut res = Self {
            nodes: n,
            lines: counts,
            directed: false,
            weight: e,
        };
        res.fit();
        res
    }
}

impl<K, C> MapIterator<K> for Matrix<C>
where
    K: Copy + Ord + Default + Sized,
    C: ChainBase<K> + Search<K>,
{
    #[inline]
    fn edges(&self, vex: K) -> Vec<(K, u64)> {
        if let Some(idx) = self.nodes.index(&vex) {
            self.weight[idx as usize]
                .iter()
                .enumerate()
                .filter(|(_, w)| **w > 0)
                .map(|(idx, &w)| (self.nodes.at(idx as u64).unwrap(), w))
                .collect::<Vec<_>>()
        } else {
            Vec::<(K, u64)>::new()
        }
    }
}
